package top.fengleifeng.question;

/**
 * @program: leetcode-test
 * @description:
 * @author: fengleifeng
 * @create: 2020-10-19 16:47
 **/
public class Num53最大子序和 {
    //dp
    class Solution {
        public int maxSubArray(int[] nums) {
            int maxAns = nums[0], pre = 0;
            for (int one : nums) {
                pre = Math.max(one, pre + one);
                maxAns = Math.max(maxAns, pre);
            }
            return maxAns;
        }

        public int maxSubArray3(int[] nums) {
            int ans = nums[0];
            int sum = 0;
            for (int num : nums) {
                if (sum > 0) {
                    sum += num;
                } else {
                    sum = num;
                }
                ans = Math.max(ans, sum);
            }
            return ans;
        }

        public int maxSubArray2(int[] nums) {
            if (nums.length <= 0) {
                return 0;
            }
            int max = Integer.MIN_VALUE;
            int[][] dp = new int[nums.length][nums.length];
            for (int i = 0; i < dp.length; i++) {
                for (int j = i; j < dp[i].length; j++) {
                    if (i == j) {
                        dp[i][j] = nums[i];
                    } else {
                        dp[i][j] = dp[i][j - 1] + nums[j];
                    }
                    max = Math.max(max, dp[i][j]);
                }
            }
            return max;
        }
    }

    public static void main(String[] args) {
        int[] ints = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int i = new Num53最大子序和().new Solution().maxSubArray(ints);
        System.out.println(i);
    }
}
